import com.google.gson.JsonArray;

import java.util.Random;

/**
 * 模拟退火主算法类
 * ======================================
 * USER NAME: ving <904679843@qq.com>
 * DATE TIME: 17-9-9 下午1:50
 * ======================================
 */
public class SA {
    private double speed;                // 退火速度
    private double tempTemperature;      // 当前温度
    private double minsTemperature;      // 最低温度
    private double iterationLength;      // 迭代次数

    private double[][] distance; // 距离矩阵

    private int[] bestPath;// 最佳路径
    private int[] tempPath;// 当前最佳路径

    private int bestLength;// 最佳路长
    private int tempLength;// 当前最佳路长

    private int startID;
    private int cityNum;

    private Random random;

    /**
     * 模拟算法构造函数
     * @param city  城市数据对象
     * @param id    以某个城市为起点的id
     * @param a     退火速度
     * @param b     退火开始温度
     * @param c     退火最低温度
     * @param d     迭代次数
     */
    public SA(City city, int id, double a, double b, double c, double d) {
        cityNum = city.getCityNum();
        startID = id;

        distance = city.getDistance();
        bestPath = new int[cityNum];
        tempPath = new int[cityNum];


        this.speed = a;
        this.tempTemperature = b;
        this.minsTemperature = c;
        this.iterationLength = d;

        bestLength = Integer.MAX_VALUE;
        tempLength = Integer.MAX_VALUE;

        random = new Random();

    }

    /**
     * SA求解
     */
    public void solve() {

        bestPath = SATool.shufflePath(cityNum, startID);              //随机生成路径解
        bestLength = SATool.calculatePathLength(distance,bestPath);   //获取路径总长

        while (minsTemperature < tempTemperature) {
            for (int i = 0; i < iterationLength; i++) {

                SATool.shuffleChangeOldPathToNewPath(bestPath,tempPath);      //随机交换 生成新的路径解  复制给 当前路径解
                tempLength = SATool.calculatePathLength(distance,tempPath);   //计算当前路径解的总路长

                if (tempLength < bestLength) {              //当前路径总长 优于 最佳路径总长  接受此解
                    SATool.copyPath(tempPath,bestPath);     //将当前路径解复制给最佳路径解
                    bestLength = tempLength;
                } else {
                    //当前路径总长 不优于 最佳路径总长 以一定概率接受该解，并且这个概率会越来越小 逐渐降低才能趋向稳定
                    if (Math.exp((bestLength - tempLength) / tempTemperature) > random.nextFloat()) {
                        SATool.copyPath(tempPath,bestPath);
                        bestLength = tempLength;
                    }
                }
            }

            tempTemperature *= speed;   //逐渐降低温度
        }
    }

    /**
     * 获取最佳的路径
     *
     * @return
     */
    public int[] getBestPath() {
        return bestPath;
    }

    /**
     * 获取最佳路径的路长
     *
     * @return
     */
    public int getBestLength() {
        return bestLength;
    }

}
